These years, studies have been made to minimize the symbol error rate by making soft-output of a result of decoding of an inner code in a concatenated code and a result of each repetitive decoding based on the repetitive decoding method, and suitable decoding methods for the error rate minimization have actively been studied. As a typical example, there is already known the BCJR algorithm proposed by Bahl, Cocke, Jelinek and Raviv in their “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate” (IEEE Trans. Inf. Theory, vol. IT-20, pp. 284–287, March 1974). The BCJR algorithm does not output each symbol as a result of decoding but it outputs the likelihood of each symbol. Such an output is called “soft-output”. What the BCJR algorithm is will be described below. In the following description, it will be assumed that as shown in FIG. 1, an encoder 1001 included in a transmitter (not shown) makes convolutional coding of digital information, and the output of the transmitter is supplied to a receiver (not shown) via a noisy non-storage communications channel 1002, and decoded, for observation, by a decoder 1003 included in the receiver.
First, a number M of states (transition state) representing the content of a shift register included in the encoder 1001 are denoted by m(0, 1, . . . , M-1), and a state at a time t is denoted by St. On the assumption that k-bit information is supplied in one time slot, an input at the time t is denoted by it=(it1, it2, . . . , itk) and an input sequence is denoted by ItT=(i1, i2, . . . , iT). In case there is a transition from a state m′ to a state m at this time, an information bit corresponding to the transition is denoted by i(m′, m)=(i1(m′, m), i2(m′, m), . . . , ik(m′, m)). Further, on the assumption that an n-bit code is outputted in one time slot, an output at the time t is denoted by Xt=(xt1, xt2, . . . . , xtn) and an output sequence is denoted by X1T=(x1, x2, . . . , xT). In case there is a transition from the state m′ to the state m at this time, a code bit for the transition is denoted by X(m′, m)=(x1(m′, m), x2(m′, m), . . . , xn(m′, m)).
It is assumed that the convolutional coding by the encoder 1001 begins with a state S0=0 and ends with ST=0 with outputting X1T. The probability Pt(m|m′) of a transition from one state to another is defined by the following expression (1):Pt(m|m′)=Pr{St=m|St−1=m′}  (1)
Note that in the right side of the expression (1), Pr{A|B} is a conditional probability in which A will occur under the same conditions as those under which B has occurred. The probability of transition Pt(m|m′) is equal to the probability Pr{it=i} in which the input it at the time t is i when the input i transits from the state m′ to state m, as will be seen from the following expression (2):Pt(m|m′)=Pr{it=i}  (2)
Supplied with X1T as an input, the noisy non-storage communications channel 1002 outputs Y1T. On the assumption that an n-bit received value is outputted in one time slot, an output at the time t will be yt=(yt1, yt2, . . . , ytn) and the output of the channel will be Y1T=(y1, y2, . . . , yT). The transition probability of the noisy non-storage channel 1002 can be defined by a transition probability Pr{yj|xj} of each symbol for all times t(1≦t≦T) as given by the following expression (3):
                    Pr        ⁢                  {                                                                      Y                  1                  t                                ⁢                                                                        X                    1                    t                                                              }                        =                                          ∏                                  j                  =                  1                                t                            ⁢                                                          ⁢                              Pr                ⁢                                  {                                                            y                      j                                        ⁢                                                                                        x                        j                                            }                                                                                                                              (        3        )            
The likelihood of input information at a time t when Y1T is received is denoted by λtj as defined by the following expression (4). This is the very thing to be determined, namely, a soft-output.
                              λ                      t            ⁢                                                  ⁢            j                          =                                            Pr              ⁢                              {                                                      i                    tj                                    =                                      1                    ⁢                                                                                        Y                        1                        T                                                                                                                  }                                              Pr              ⁢                              {                                                      i                    tj                                    =                                      0                    ⁢                                                                                        Y                        1                        T                                                                                                                  }                                              (        4        )            
In the BCJR algorithm, probabilities αt, βt and γt as shown in the following expressions (5) and (7) are defined. Note that Pr{A; B} is a probability in which both A and B will occur.αt(m)=Pr{St=m;Y1t}  (5)βt(m)=Pr{Yt+1T|St=m}  (6)γt(m′,m)=Pr{St=m; yt|St−1=m′}  (7)
What these probabilities αt, βt and γt are will be described with reference to FIG. 2 showing a trellis which provides a diagram of state transition taking place in the encoder 1001. In FIG. 2, αt−1 corresponds to a probability of passing by each state at a time t−1 computed from a coding start state S0=0 in time sequence on the basis of a received value; βt corresponds to a probability of passing by each state at a time t computed from a coding termination state ST=0 in reverse time sequence on the basis of the received value; and γt corresponds to a probability of reception of an output of each branch runs from one state to another at the time t computed on the basis of a received value and input probability at the time t.
Using these probabilities αt, βt and γt, the soft-output λtj can be given by the following expression (8):
                              λ          tj                =                                            ∑                                                                    i                    j                                    ⁡                                      (                                                                                                                                                      m                              ′                                                        ,                            m                                                                                                                                                                                                          m                              ′                                                        ,                            m                                                                                                                )                                                  =                1                                      ⁢                                                            α                  t                                ⁡                                  (                                      m                    ′                                    )                                            ⁢                                                γ                  t                                ⁡                                  (                                                            m                      ′                                        ,                    m                                    )                                            ⁢                                                β                  t                                ⁡                                  (                  m                  )                                                                                        ∑                                                                    i                    j                                    ⁡                                      (                                                                                                                                                      m                              ′                                                        ,                            m                                                                                                                                                                                                          m                              ′                                                        ,                            m                                                                                                                )                                                  =                0                                      ⁢                                                            α                  t                                ⁡                                  (                                      m                    ′                                    )                                            ⁢                                                γ                  t                                ⁡                                  (                                                            m                      ′                                        ,                    m                                    )                                            ⁢                                                β                  t                                ⁡                                  (                  m                  )                                                                                        (        8        )            
The relation among the times t=1, 2, . . . , T can be given by the following expression (9):
                                                        α              t                        ⁡                          (              m              )                                =                                    ∑                                                m                  ′                                =                0                                            M                -                1                                      ⁢                                                            α                                      t                    -                    1                                                  ⁡                                  (                                      m                    ′                                    )                                            ⁢                                                γ                  t                                ⁡                                  (                                                            m                      ′                                        ,                    m                                    )                                                                    ⁢                                  ⁢                                            where              ⁢                                                          ⁢                                                α                  0                                ⁡                                  (                  0                  )                                                      =            1                    ,                                                    α                0                            ⁡                              (                m                )                                      =                          0              ⁢                                                (                                      m                    ≠                    0                                    )                                .                                                                        (        9        )            
The above relation among the times t=1, 2, . . . , T can also be given by the following expression (10):
                                                        β              t                        ⁡                          (              m              )                                =                                    ∑                                                m                  ′                                =                0                                            M                -                1                                      ⁢                                                            β                                      t                    +                    1                                                  ⁡                                  (                                      m                    ′                                    )                                            ⁢                                                γ                                      t                    +                    1                                                  ⁡                                  (                                      m                    ,                                          m                      ′                                                        )                                                                    ⁢                                  ⁢                                            where              ⁢                                                          ⁢                                                β                  T                                ⁡                                  (                  0                  )                                                      =            1                    ,                                                    β                T                            ⁡                              (                m                )                                      =                          0              ⁢                                                (                                      m                    ≠                    0                                    )                                .                                                                        (        10        )            
Further, the probability γt can be given by the following expression (11):
                                          γ            t                    ⁡                      (                                          m                ′                            ,              m                        )                          =                  {                                                                                                                                                                                                                                                                                                                                  P                                    t                                                                    (                                  m                                                                                                                            ⁢                                                              m                                ′                                                                                      )                                                    ·                          Pr                                                ⁢                                                  {                                                      y                            t                                                                                                                                      ⁢                                          x                      ⁡                                              (                                                                              m                            ′                                                    ,                          m                                                )                                                                              }                                                                                                                                                              ⁢                                                            =                                                                                                    Pr                            ⁢                                                                                          {                                                                                                      i                                    t                                                                    =                                                                      i                                    ⁡                                                                          (                                                                                                                        m                                          ′                                                                                ,                                        m                                                                            )                                                                                                                                      }                                                            ·                              Pr                                                        ⁢                                                          {                                                              y                                t                                                                                                                                                              ⁢                                                  x                          ⁡                                                      (                                                                                          m                                ′                                                            ,                              m                                                        )                                                                                                                }                                                                                                                                                                                ⁢                                      :                                          Transition                      ⁢                                                                                          ⁢                      from                      ⁢                                                                                          ⁢                                              m                        ′                                            ⁢                                                                                          ⁢                      to                      ⁢                                                                                          ⁢                      m                      ⁢                                                                                          ⁢                      with                      ⁢                                                                                          ⁢                      input                      ⁢                                                                                          ⁢                      i                                                                                                                                            0                  ⁢                                                                          :                                      No                    ⁢                                                                                  ⁢                                          tr                      ⁢                      ansition                                        ⁢                                                                                  ⁢                    from                    ⁢                                                                                  ⁢                                          m                      ′                                        ⁢                                                                                  ⁢                    to                    ⁢                                                                                  ⁢                    m                    ⁢                                                                                  ⁢                    with                    ⁢                                                                                  ⁢                    input                    ⁢                                                                                  ⁢                    i                                                                                                          (        11        )            
Therefore, to adopt the BCJR algorithm for the soft-output decoding, the decoder 1003 determines a soft-output λt based on the above-mentioned relations by running through a sequences of operational steps in a flow chart shown in FIG. 3.
First in step S1001 shown in FIG. 3, each time the decoder 1003 receives yt, it computes probabilities αt(m) and γt(m′, m) based on the above expressions (9) and (11).
Next in step S1002, after receiving all data in the sequence Y1T, the decoder 1003 computes a probability βt(m) of each state m at all times t on the basis of the above expression (10).
Then in step S1003, the decoder 1003 computes the soft-output λt at each time t by placing, into the above expression (8), the probabilities αt, βt and γt having been computed in steps S1001 and S1002.
Going through the above sequences of operational steps, the decoder 1003 can make the soft-output decoding by adopting the BCJR algorithm.
It should be reminded here that the BCJR algorithm has a problem that since the computational operations have to be done with a probability being held as it is as a value and include a product operation, so this algorithm needs large amounts of computation. To reduce the amounts of computation, there are available the Max-Log-MAP and Log-Map algorithms (will be referred to as “Max-Log-BCJR algorithm” and “Log-MCJR algorithm”, respectively, hereunder) proposed by Robertson, Villebrun and Hoeher in their “A Comparison of Optimal and Sub-optimal MAP Decoding Algorithms Operating in the Domain” (IEEE Int. Conf. on Communications, pp. 1009–1013, June 1995).
First, the Max-Log-BCJR algorithm will be explained. In this algorithm, the probabilities αt, βt, and γt and the soft-output λt are logarithmically notated by natural logarithms, respectively, the product operation for the probabilities is replaced with a logarithmic-sum operation as shown in the following expression (12), and the sum operation for the probabilities is approximated by computation of a logarithmic maximum value as shown in the following expression (13). Note that max(x, y) in the following expression (13) is a function to select “x” or “y”, whichever has a larger value.log(ex·ey)=x+y  (12)log(ex+ey)=max(x+y)  (13)
To simplify the description, the natural logarithm is represented by I, and the natural logarithms of the probabilities αt, βt and γt and soft-output λt are represented by Iαt, Iβt, Iγt and Iλt, respectively, as shown in the following expression (14). Note that “sgn” in the expression (14) is a constant indicating a sign which provides a discrimination between positive and negative, that is, “+1” or “−1”.
                    {                                                                                                                                                I                        ⁢                                                                                                  ⁢                                                                              α                            t                                                    ⁡                                                      (                            m                            )                                                                                              =                                              sgn                        ·                                                  log                          ⁡                                                      (                                                                                          α                                t                                                            ⁡                                                              (                                m                                )                                                                                      )                                                                                                                                                                                                                                  I                        ⁢                                                                                                  ⁢                                                                              β                            t                                                    ⁡                                                      (                            m                            )                                                                                              =                                              sgn                        ·                                                  log                          ⁡                                                      (                                                                                          β                                t                                                            ⁡                                                              (                                m                                )                                                                                      )                                                                                                                                                                                                                                  I                        ⁢                                                                                                  ⁢                                                                              γ                            t                                                    ⁡                                                      (                            m                            )                                                                                              =                                              sgn                        ·                                                  log                          ⁡                                                      (                                                                                          γ                                t                                                            ⁡                                                              (                                m                                )                                                                                      )                                                                                                                                                                                                                                        I                  ⁢                                                                          ⁢                                      λ                    t                                                  =                                                      sgn                    ·                    log                                    ⁢                                                                          ⁢                                      λ                    t                                                                                                          (        14        )            
The reason why such a constant sgn is given is that since each of the probabilities αt, βt and γt takes a value ranging from 0 to 1, each of the computed logarithmic likelihood Iαt, Iβt and Iγt takes a negative value in principle.
For example, in case the decoder 1003 is constructed as a software, the constant sgn may be either “+1” or “−1” because the decoder 1003 can process any value, positive or negative. In case the decoder 1003 is constructed as a hardware, the positive/negative discrimination sign for a computed negative value should desirably be inverted and handled as a positive value in order to reduce the number of bits.
More particularly, in case the decoder 1003 is constructed as a system in which only negative values are handled as a log likelihood, the constant sgn takes “+1”. On the other hand, in case the decoder 1003 is constructed as a system in which only positive values are handled as a log likelihood, the constant sgn takes “−1”. In the following, the algorithms will be described with consideration given to the above.
In the Max-Log-BCJR algorithm, each of the log likelihood Iαt, Iβt and Iγt is approximated as shown in the following expressions (15) to (17). The term “msgn(x, y)” in the expressions (15) and (16) indicates a function max(x, y) by which x or y, whichever has a larger value, is selected when the constant sgn is “+1”, while it indicates a function min(x, y) by which x or y, whichever is smaller in value, is selected when the constant sgn is “−1”. It is assumed here that the function msgn(x, y) in the state m′ at the right side of the expression (15) is determined within the state m′ in which there exists a transition to the state m, while the function msgn(x, y) in the state m′ at the right side of the expression (16) is determined within the state m′ in which there exists a transition from the state m.
                              I          ⁢                                          ⁢                                    α              t                        ⁡                          (              m              )                                      ≃                              msgn                          m              ′                                ⁡                      (                                          I                ⁢                                                                  ⁢                                                      α                                          t                      -                      1                                                        ⁡                                      (                                          m                      ′                                        )                                                              +                              I                ⁢                                                                  ⁢                                                      γ                    t                                    ⁡                                      (                                                                  m                        ′                                            ⁢                      m                                        )                                                                        )                                              (        15        )                                          I          ⁢                                          ⁢                                    β              t                        ⁡                          (              m              )                                      ≃                              msgn                          m              ′                                ⁡                      (                                          I                ⁢                                                                  ⁢                                                      β                                          t                      +                      1                                                        ⁡                                      (                                          m                      ′                                        )                                                              +                              I                ⁢                                                                  ⁢                                                      γ                                          t                      +                      1                                                        ⁡                                      (                                          m                      ,                                              m                        ′                                                              )                                                                        )                                              (        16        )            Iγt(m′,m)=sgn·(log(Pr{it=i(m′,m)})+log(Pr{yt|x(m′,m)}))  (17)
With the Max-Log-BCJR algorithm, also the log soft-output Iλt is similarly approximated as given by the following expression (18). It is assumed here that the function msgn in the first term at the right side of the expression (18) is determined within the state m′ in which there exists a transition to the state m when the decoder 1003 is supplied with an input of “1”, while the function msgn in the second term is determined within the state m′ in which there exists a transition to the state m when the decoder 1003 is supplied with an input of “0”.
                              I          ⁢                                          ⁢                      λ                          t              ⁢                                                          ⁢              j                                      ≃                                            msgn                                                                    m                    ′                                    ⁢                  m                                                                                            i                      j                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                        =                  1                                                      ⁡                          (                                                I                  ⁢                                                                          ⁢                                                            α                                              t                        -                        1                                                              ⁡                                          (                                              m                        ′                                            )                                                                      +                                  I                  ⁢                                                                          ⁢                                                            γ                      t                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                                      +                                  I                  ⁢                                                                          ⁢                                                            β                      t                                        ⁡                                          (                      m                      )                                                                                  )                                -                                          ⁢                                          ⁢                                    msgn                                                                    m                    ′                                    ⁢                  m                                                                                            i                      j                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                        =                  0                                                      ⁡                          (                                                I                  ⁢                                                                          ⁢                                                            α                                              t                        -                        1                                                              ⁡                                          (                                              m                        ′                                            )                                                                      +                                  I                  ⁢                                                                          ⁢                                                            γ                      t                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                                      +                                  I                  ⁢                                                                          ⁢                                                            β                      t                                        ⁡                                          (                      m                      )                                                                                  )                                                          (        18        )            
Therefore, when making soft-output decoding with the Max-Log-BCJR algorithm, the decoder 1003 goes through a sequences of operational steps in a flow chart shown in FIG. 4 to determine a soft-output λt on the basis of the above relations.
First in step S1011 in FIG. 4, each time the decoder 1003 receives yt, it computes log likelihood Iαt(m) and Iλt(m′ m) on the basis of the above expressions (15) and (17).
Then in step S1012, after receiving all data in the sequence Y1T, the decoder 1003 computes a log likelihood Iβt(m) for each state m at all times t on the basis of the expression (16).
Then in step S1013, the decoder 1003 places, in the expression (18), the log likelihood Iαt, Iβt and Iγt having been computed in steps S1011 and S1012 to compute a log soft-output Iλt at each time t.
Going through the above sequences of operational steps, the decoder 1003 can make the soft-output decoding with the Max-Log-BCJR algorithm.
Thus, since the Max-Log-BCJR algorithm includes no product operation, it permits to determine any desired value with considerably smaller amounts of computation than the BCJR algorithm.
Next, the Log-BCJR algorithm will be described. This algorithm is a version of the Max-Log-BCJR algorithm, which permits an approximation with a higher accuracy. More particularly, with the Log-BCJR algorithm, the probability sum operation shown in the expression (13) is deformed by adding a correction term as given by the following expression (19), to determine a correct log value by the sum operation. Such a correction will be called “log-sum correction”.log(ex+ey)=max(x, y)+(1+e−|x−y|)  (19)
The operation at the left side of the expression (19) will be called “log-sum operation”. According to the numeration system described in “Implementation and Performance of A Turbo/MAP Decoder” (S. S. Pietrobon; Int. J. Satellite Commun., vol. 16, pp. 23–46, January–February 1998), the operator for this log-sum operation will be denoted by “#” (which is “E” in the Pietrobon's paper) as in the following expression (20) for convenience' sake.x#y=log(ex+ey)  (20)
Note that the expressions (19) and (20) are for the above constant sgn of “+1” but when the constant sgn is “−1”, operations corresponding to the expressions (19)and (20) are as given by the following expressions (21) and (22), respectively:−log(e−x+e−y)=min(x, y)−log(1+e−|x−y|)  (21)x#y=−log(e−x+e−y)  (22)
Further, the operator for the cumulative add operation in the log-sum operation will be denoted by “#Σ” (which is “E” in the paper) as given by the following expression (23).
                              #          ⁢                                          ⁢                                    ∑                              i                =                0                                            M                -                1                                      ⁢                          x              i                                      =                  (                                    (                                                          ⁢                              …                ⁢                                                                  ⁢                                  (                                                            (                                                                        x                          0                                                ⁢                                                                                                  ⁢                        #                        ⁢                                                                                                  ⁢                                                  x                          1                                                                    )                                        ⁢                                                                                  ⁢                    #                    ⁢                                                                                  ⁢                                          x                      2                                                        )                                ⁢                                                                  ⁢                …                            ⁢                                                          )                        ⁢                                                  ⁢            #            ⁢                                                  ⁢                          x                              M                -                1                                              )                                    (        23        )            
Using the above operators, the log likelihood Iαt and Iβt and log soft-output Iλt in the Log-BCJR algorithm may be denoted as given by the following expressions (24) to (26), respectively. Note that since the log likelihood Iγt is denoted as given by the above expression (17), it will not be described.
                              I          ⁢                                          ⁢                                    α              t                        ⁡                          (              m              )                                      =                  #          ⁢                                          ⁢                                    ∑                                                m                  ′                                =                0                                            M                -                1                                      ⁢                          (                                                I                  ⁢                                                                          ⁢                                                            α                                              t                        -                        1                                                              ⁡                                          (                                              m                        ′                                            )                                                                      +                                  I                  ⁢                                                                          ⁢                                                            γ                      t                                        ⁡                                          (                                                                        m                          ′                                                ,                        m                                            )                                                                                  )                                                          (        24        )                                          I          ⁢                                          ⁢                                    β              t                        ⁡                          (              m              )                                      =                  #          ⁢                                          ⁢                                    ∑                                                m                  ′                                =                0                                            M                -                1                                      ⁢                          (                                                I                  ⁢                                                                          ⁢                                                            β                                              t                        +                        1                                                              ⁡                                          (                                              m                        ′                                            )                                                                      +                                  I                  ⁢                                                                          ⁢                                                            γ                                              t                        +                        1                                                              ⁡                                          (                                              m                        ,                                                  m                          ′                                                                    )                                                                                  )                                                          (        25        )                                          I          ⁢                                          ⁢                      λ            tj                          =                              #            ⁢                                                  ⁢                                          ∑                                                                            i                      j                                        ⁡                                          (                                                                                                                                                                  m                                ′                                                            ,                              m                                                                                                                                                                                                                          m                                ′                                                            ,                              m                                                                                                                          )                                                        =                  1                                            ⁢                              (                                                      I                    ⁢                                                                                  ⁢                                                                  α                                                  t                          -                          1                                                                    ⁡                                              (                                                  m                          ′                                                )                                                                              +                                      I                    ⁢                                                                                  ⁢                                                                  γ                        t                                            ⁡                                              (                                                                              m                            ′                                                    ,                          m                                                )                                                                              +                                      I                    ⁢                                                                                  ⁢                                                                  β                        t                                            ⁡                                              (                        m                        )                                                                                            )                                              -                      #            ⁢                                                  ⁢                                          ∑                                                                            i                      j                                        ⁡                                          (                                                                                                                                                                  m                                ′                                                            ,                              m                                                                                                                                                                                                                          m                                ′                                                            ,                              m                                                                                                                          )                                                        =                  0                                            ⁢                              (                                                      I                    ⁢                                                                                  ⁢                                                                  α                                                  t                          -                          1                                                                    ⁡                                              (                                                  m                          ′                                                )                                                                              +                                      I                    ⁢                                                                                  ⁢                                                                  γ                        t                                            ⁡                                              (                                                                              m                            ′                                                    ,                          m                                                )                                                                              +                                      I                    ⁢                                                                                  ⁢                                                                  β                        t                                            ⁡                                              (                        m                        )                                                                                            )                                                                        (        26        )            
Note that the operator for the cumulative add operation in the log-sum operation in the state m′ at the right side of the above expression (24) will be determined in the state m′ in which there exists a transition to the state m and the operator for the cumulative add operation in the log-sum operation in the state m′ at the right side of the above expression (25) will be determined in the state m′ in which there exists a transition from the state m. Also, the operator for the cumulative add operation in the log-sum operation in the first term at the right side of the above expression (26) will be determined in the state m′ in which there exists a transition to the state m when the input is “1”, while the operator for the cumulative add operation in the log-sum operation in the second term will be determined in the state m′ in which there exists a transition to the state m when the input is “0”.
Therefore, when making soft-output decoding with the Log-BCJR algorithm, the decoder 1003 goes through the sequences of operational steps in the flow chart shown in FIG. 4 to determine a soft-output λt on the basis of the above relations.
First in step S1011 in FIG. 4, each time the decoder 1003 receives yt, it computes log likelihood Iαt(m) and Iγt(m′ m) based on the above expressions (24) and (17).
Then in step S1012, after receiving all data in the sequence Y1T, the decoder 1003 computes a log likelihood Iβt(m) for each state m at all times t based on the expression (25).
Then in step S1013, the decoder 1003 computes a log soft-output Iλt at each time t by placing, in the expression (26), the log likelihood Iαt, Iβt and Iγt having been computed in steps S1011 and S1012.
Going through the above sequences of operational steps, the decoder 1003 can make the soft-output decoding with the Log-BCJR algorithm. Note that since in the above expressions (19) and (21), the correction term in the second term at the right side is represented by a one-dimensional function for a variable |x−y|, the decoder 1003 can accurately compute a probability by pre-storing the values of the corrective term as a table in a ROM (read-only memory) (not shown).
The Log-BCJR algorithm needs more operations than the Max-Log-BCJR algorithm but does not include any product operation, and its output except for a quantize error is the very log value of a BCJR algorithm soft-output.
It should be reminded that the BCJR algorithm, Max-Log-BCJR algorithm or Log-BCJR algorithm permitting to decode trellis codes such as convolutional code or the like may be used for decoding a code generated by using the trellis code as an element code and concatenating a plurality of element encoders via an interleaver. That is, the BCJR, Max-Log BCJR or Log-BCJR algorithm can be used for decoding a parallel concatenated convolutional codes (will be referred to as “PCCC” hereunder) or serially concatenated convolutional codes (will be referred to as “SCCC” hereunder), or turbo trellis-coded modulation (will be referred to as “TTCM” hereunder) or serial concatenated trellis-coded modulation (will be referred to as “SCTCM” hereunder), in which the PCCC or SCCC is combined with a multi-valued modulation and signal point mapping and error correction code decoding characteristic are collectively put in consideration.
A decoder to decode any of the above PCCC, SCCC, TTCM and SCTCM codes will make a so-called repetitive decoding by a plurality of element decoders each destined to make a maximum a posteriori probability (MAP) decoding based on the BCJR, Max-Log-BCJR or Log-BCJR algorithm.
It should be reminded that in case a code to be decoded is a punctured one or in a similar case, each of the element decoders has to be supplied with erasure position information, indicative of a position where there is not any coded output such as a puncture position or the like, as information necessary for the soft-output decoding. The erasure position information has to be held separately at least until a log likelihood Iγ is computed. To this end, each of the decoders should be provided with a memory circuit to hold the erasure position information, for example, which has been a cause of an increased circuit scale.
Decoding of a code whose parallel paths exist in a trellis will be discussed herebelow. In this case, though the parallel paths can be regarded as a single path because its transition origins are same in state and transition destinations are also same in state, each element decoder has to decode the parallel paths as two paths. Especially when computing log likelihood Iα and Iβ, a larger number of paths have to be considered, and so the processing burden to each of the element decoders will be larger.
Also, when computing a log soft-output Iλ, each element decoder has to predetermine the sum of log likelihood Iα and Iλ. Namely, to compute the log soft-output Iλ, each element decoder should normally be provided with a separate circuit to compute the sum of log likelihood Iα and Iγ. Thus, in each of the element decoders, the circuit to compute the log soft-output Iλ will possibly be increased in scale.